package leetcode.editor.offer;

// 33. 二叉搜索树的后序遍历序列
// https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/
class ErChaSouSuoShuDeHouXuBianLiXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
        solution.verifyPostorder(new int[]{4, 6, 7, 5});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        // 递归法
        public boolean verifyPostorder(int[] postorder) {
            return traversal(postorder, 0, postorder.length - 1);
        }

        public boolean traversal(int[] postorder, int left, int right) {
            if (left >= right) {
                return true;
            }

            int index = left;
            while (postorder[index] < postorder[right]) index++;
            int temp = index;
            while (postorder[temp] > postorder[right]) temp++;

            return temp == right && traversal(postorder, left, index - 1) && traversal(postorder, index, right - 1);
        }

        // 单调栈
        /*public boolean verifyPostorder(int[] postorder) {
            Stack<Integer> stack = new Stack<>();
            int rootVal = Integer.MAX_VALUE;
            // 到后序遍历
            for (int i = postorder.length - 1; i >= 0; i--) {
                if (postorder[i] > rootVal) return false;
                while (!stack.isEmpty() && postorder[i] < stack.peek()) {
                    rootVal = stack.pop();
                }
                stack.push(postorder[i]);
            }

            return true;
        }
*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
